import java.util.HashMap;
import java.util.Map;

/**
 * 删除重复的节点，通过hashMap 计数版本。
 */
public class JavaDemo5 {
    public static void main(String[] args) {
        int[] arrays = {1, 2, 2, 3, 3, 4, 5, 5};
        ListNode head = new ListNode(arrays[0]);
        ListNode next = head;
        for (int i = 1; i < arrays.length; i++) {
            ListNode node = new ListNode(arrays[i]);
            next.next = node;
            next = node;
        }
        ListNode showParent = head;
        while (showParent != null) {
            System.out.println(showParent.val);
            showParent = showParent.next;
        }
        System.out.println("---------------");
        showParent = deleteDuplicates(head);
        while (showParent != null) {
            System.out.println(showParent.val);
            showParent = showParent.next;
        }
    }

    static public ListNode deleteDuplicates(ListNode head) {
        Map<Integer, Integer> map = new HashMap<>();
        ListNode cur = head;
        while (cur != null) {
            if (map.containsKey(cur.val)) {
                map.put(cur.val, map.get(cur.val) + 1);
            } else {
                map.put(cur.val, 1);
            }
            cur = cur.next;
        }
        ListNode res = new ListNode(-1);
        res.next = head;
        cur = res;
        while (cur!=null){
            if (cur.next!=null){
                if (map.get(cur.next.val)!=1){
                    cur.next=cur.next.next;
                }else {
                    cur=cur.next;
                }
            }else {
                cur= null;
            }

        }
        return res.next;
    }

}
